package week_2.homework;

import week_1.practice.EmptyCollectionException;

/*deque这个名字代表双端队列（double ended queue）。这两者的区别在于，deque中可以在队列的任何一端进行插入和删除，
* pp5.7就是用链表来实现deque*/

public class deque<T> implements QueueADT_5_7<T> {

    private int count;
    private LinearNode<T> head, tail;

    public deque(){
        count = 0;
        head = tail = null;
    }
    /*往队列的前端添加一个元素*/
    @Override
    public void enqueueHead(T element)
    {
        LinearNode<T> node = new LinearNode<T>(element);

        if (isEmpty())
        {
            tail = node;
        }
        else
        {
            head.setPrevious(node);
        }
        node.setNext(head);
        head = node;
        count++;
    }

    /*往队列的后端添加一个元素*/
    @Override
    public void enqueueLast(T element) {
        LinearNode<T> node = new LinearNode<T>(element);

        if (isEmpty()) {
            head = node;
        } else {
            tail.setNext(node);
        }
        node.setPrevious(tail);
        tail = node;
        count++;


    }
    /*从队列中前端移除一个元素*/
    @Override
    public T dequeueHead() throws EmptyCollectionException {
        if (isEmpty())
            throw new EmptyCollectionException("queue");
        LinearNode<T> temp = head;
        head = head.getNext();
        if (head != null) {
            head.setPrevious(null);
        } else {
            tail = null;
        }
        count--;
        return temp.getElement();

    }

    /*从队列中末端移除一个元素*/
    @Override
    public T dequeueLast() throws EmptyCollectionException {
        if (isEmpty())
            throw new EmptyCollectionException("queue");
        LinearNode<T> temp = tail;
        tail = tail.getPrevious();
        if (tail != null) {
            tail.setNext(null);
        } else {
            head = null;
        }
        count--;
        return temp.getElement();
    }
    /*考察队列前端的那个元素 */
    @Override
    public T first() throws EmptyCollectionException {
        if(isEmpty())
            throw new EmptyCollectionException("queue");

        return head.getElement();
    }
    /*考察队列末端的那个元素 */
    @Override
    public T Last() throws EmptyCollectionException {
        if(isEmpty())
            throw new EmptyCollectionException("queue");

        return tail.getElement();
    }
    /*判定队列是否为空*/
    @Override
    public boolean isEmpty() {
        if (count == 0)
            return true;
        else
            return false;
    }
    /*判定队列中的元素数目*/
    @Override
    public int size() {
        return count;
    }
    /*返回队列的字符串表示*/
    public String toString(){
        String result = "";
        LinearNode<T> current = head;
        for(int a=0;a<count;a++)
        {
            result += current.getElement() + " ";
            current = current.getNext();
        }

        return result;
    }
}